package leetcode;

/**
 * Created by Ghost on 2015/2/4 0004.
 */
public class First_Missing_Positive {
    public int firstMissingPositive(int[] A) {
        if(A==null || A.length==0)
            return 1;
        for (int i = 0; i < A.length; i++) {
            int cur = A[i];
            while (cur >= 1 && cur - 1 < A.length) {
                int tmp = A[cur - 1];
                if(A[cur-1]!=cur){
                    A[cur - 1] = cur;
                    cur = tmp;

                }
                else
                    break;
            }
        }


        for(int i=0;i<A.length;i++){
            if(A[i]!=i+1){
                return i+1;
            }
        }
        return A[A.length-1]+1;
    }

    public static void main(String[] args){
        First_Missing_Positive first_missing_positive = new First_Missing_Positive();
        int[] A = {1};
        System.out.println(first_missing_positive.firstMissingPositive(A));
    }
}
